#pragma once
#include <iostream>
#include <algorithm>
#include <stdbool.h>
namespace bit {
	template<class T>
	struct ListNode {
		ListNode<T>* next;
		ListNode<T>* prev;
		T val;
		ListNode(const T& x = T())
			:next(nullptr)
			,prev(nullptr)
			,val(x)
		{}
	 };
	template <class T , class Ref , class Ptr>
	struct Iterator {
		typedef ListNode<T> Node;
		Node* _node;
		Iterator(Node* node)
			:_node(node)
		{}
		Iterator& operator++() {
			_node = _node->next;
			return *this;
		}
		Iterator operator++(int) {
			Iterator tmp(*this);
			_node = _node->next;
			return tmp;
		}
		Iterator& operator--() {
			_node = _node->prev;
			return *this;
		}
		Iterator operator--(int) {
			Iterator tmp(*this);
			_node = _node->prev;
			return tmp;
		}
		Ref operator*() {
			return _node->val;
		}
		Ptr operator->() {
			return &_node->val;
		}
		bool operator==(const Iterator& node) {
			return _node == node._node;
		}
		bool operator!=(const Iterator& node) {
			return _node != node._node;
		}
	};
	template <class T>
	class list {
		typedef ListNode<T> Node;
	public:
		typedef Iterator<T , T&, T*> iterator;
		typedef Iterator<T, const T&, const T*> const_iterator;
		list() {
			_node = new Node;
			_node->next = _node;
			_node->prev = _node;
		}
		void push_back(const T& x) {
			insert(end(), x);
		}
		iterator begin() {
			return _node->next;
		}
		iterator end() {
			return _node;
		}
		const_iterator begin() const{
			return _node->next;
		}
		const_iterator end() const{
			return _node;
		}
		void insert(iterator pos , const T& x) {
			Node* cur = pos._node;
			Node* newnode = new Node(x);
			Node* prev = cur->prev;
			newnode->next = cur;
			cur->prev = newnode;
			newnode->prev = prev;
			prev->next = newnode;
		}
		iterator erase(iterator pos) {
			Node* tmp = pos._node;
			tmp->next->prev = tmp->prev;
			tmp->prev->next = tmp->next;
			Node* tail = tmp->next;
			delete tmp;
			return tail;
		}
		void pop_back() {
			erase(--end());
		}
		void push_front(const T& x) {
			insert(begin() , x);
		}
		void pop_front() {
			erase(begin());
		}
		size_t size() const{
			size_t n = 0;
			const_iterator it = begin();
			while (it != end())
			{
				n++;
				it++;
			}
			return n;
		}
		bool empty() {
			return size() == 0;
		}
		void clear() {
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		~list() {
			clear();
			delete _node;
			_node = nullptr;
		}
		void swap(list<T> node) {
			std::swap(_node, node._node);
		}
		list<T>& operator=(list<T> node) {
			swap(node);
			return *this;
		}
	private:
		Node* _node;
	};
}